Sześciany [A]

Limit pamięci: 64 MB

Bajtazar wymyślił nowy system podpisu półelektronicznego BajtoKrypt, w którym każdy użytkownik do podpisywania dokumentów wykorzystuje swój klucz, będący pustym w środku sześcianem o boku długości . Każda ścianka każdego sześcianu jest podzielona na kratek, z których każda może zawierać jeden chip (szyfrujący albo ogólnego przeznaczenia) albo być pusta. Wszystkie chipy szyfrujące są identyczne; podobnie każde dwa chipy ogólnego przeznaczenia są takie same. Układ chipów szyfrujących na każdej ściance każdego sześcianu jest z dokładnością do obrotu zawsze taki sam (dla każdej ścianki każdego sześcianu istnieje taki sposób jej obrotu, żeby układy chipów szyfrujących wszystkich ścianek wyglądały dokładnie tak samo); jedyne, czym mogą różnić się ścianki to to, które z pozostałych kratek są zajęte przez chipy ogólnego przeznaczenia. Ponadto wszystkie chipy są zawsze umieszczane po jednej stronie ścianki - dokładniej tej, która jest skierowana do środka sześciennego klucza.

Bajtohaker zamierza złamać system BajtoKrypt; nauczył się już idealnie podrabiać sześcienne klucze. Chciałby on wiedzieć, ile minimalnie kluczy potrzebuje, by móc podszyć się pod dowolnego użytkownika systemu. Dokładniej, dla każdego możliwego klucza użytkownika (określonego przez rozmieszczenie chipów ogólnego przeznaczenia na każdej ze ścianek i wzajemne ułożenie ścianek w ramach klucza) Bajtohaker chciałby mieć w swoim zbiorze kluczy taki, który po ewentualnym rozmontowaniu na pojedyncze ścianki, poprzekładaniu ich i poobracaniu w dowolny sposób, a następnie zmontowaniu z powrotem daje w rezultacie sześcian identyczny z rozważanym kluczem użytkownika. Dwa klucze uznajemy przy tym za identyczne, jeżeli można w taki sposób poobracać jeden z nich, aby otrzymać drugi. Żeby nie przygnębiać Bajtohakera, odpowiedź dla jego problemu podaj modulo .

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia długość boku każdego z sześciennych kluczy i opis rozmieszczenia chipów szyfrujących na każdej ze ścianek,
• obliczy minimalną liczność zbioru kluczy, który spełni wymaganie Bajtohakera,
• wypisze resztę z dzielenia wyniku przez na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita dodatnia (). W kolejnych wierszach znajduje się po liczb całkowitych (), pooddzielanych pojedynczymi odstępami. oznacza, że w -tej kratce -tego wiersza każdej ścianki znajduje się chip szyfrujący. oznacza, że kratka ta nie zawiera chipu szyfrującego, czyli może być pusta bądź wykorzystana na chip ogólnego przeznaczenia.

Wyjście

W jedynym wierszu wyjścia powinna znajdować się jedna liczba całkowita - liczba kluczy potrzebnych Bajtohakerowi modulo .

Przykład

3
1 0 0
1 1 1
0 0 1

5005

Autor zadania: Krzysztof Dulęba.